<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
  <title>Open Source Web Animation - C++ Tutorial: Linked List</title>
  <meta
 content="Open Source Web Animation C++ Tutorial: Linked List"
 name="description" />
  <meta
 content="Open Source, Web Animation, C++ Tutorial, Linked List Examples"
 name="keywords" />
  <meta http-equiv="Content-Type"
 content="text/html; charset=ISO-8859-1" />
  <link type="text/css" rel="stylesheet" href="../images/bogostyleWidePre.css" />
</head>
<body>
<div id="page" align="center">
<div id="content" style="width: 800px;">
<div id="logo">
<div class="whitetitle" style="margin-top: 70px;">bogotobogo </div>
</div>
<div id="topheader">
<div class="headerbodytext" align="left"><br />
<strong>Bogotobogo</strong><br />
contact@bogotobogo.com </div>
<div class="smallgraytext" id="toplinks"><a href="../index.html">Home</a>
| <a href="../sitemap.html">Sitemap</a>
| <a href="../blog" target="_blank">Contact Us</a>
</div>
</div>
<div id="menu">
<div class="smallwhitetext" style="padding: 9px;" align="right"><a
 href="../index.html">Home</a>
| <a href="../about_us.html">About Us</a>
| <a href="../products.html">Products</a>
| <a href="../our_services.html">Our Services</a>
| <a href="../blog" target="_blank">Contact Us</a>
</div>
</div>
<div id="submenu">
<div class="smallgraytext" style="padding: 9px;" align="right"><a
 href="../gif.html">Gif</a> |
<a href="../java_applet.html">JavaApplet/Web Start</a>
| <a href="../flash.html">Flash</a>
| <a href="../shockwave.html">ShockWave</a>
| <a href="../svg.html">SVG</a>
| <a href="../iPhone.html">iPhone/iPad</a>
| <a href="../android.html">Android</a>
</div>
</div>

<div id="contenttext">

<!-- Use of this code assumes agreement with the Google Custom Search Terms of Service. -->
<!-- The terms of service are available at http://www.google.com/cse/docs/tos.html -->
<form name="cse" id="searchbox_demo" action="http://www.google.com/cse">
  <input type="hidden" name="cref" value="" />
  <input type="hidden" name="ie" value="utf-8" />
  <input type="hidden" name="hl" value="" />
  <input name="q" type="text" size="40" />
  <input type="submit" name="sa" value="Search" />
</form>
<script type="text/javascript" src="http://www.google.com/cse/tools/onthefly?form=searchbox_demo&lang="></script>

<div id="bookmarkshare">
<script type="text/javascript">var addthis_config = {"data_track_clickback":true};</script>
<a class="addthis_button" href="http://www.addthis.com/bookmark.php?v=250&amp;username=khhong7"><img src="http://s7.addthis.com/static/btn/v2/lg-share-en.gif" width="125" height="16" alt="Bookmark and Share" style="border:0"/></a><script type="text/javascript" src="http://s7.addthis.com/js/250/addthis_widget.js#username=khhong7"></script>
</div>

<br />
<div style="padding: 10px;"><span class="titletext">C++ Tutorial - Linked List Examples</span></div>
<img src="../images/cplusplus/cpp_logo.jpg" alt="cplusplus logo"/>

<div class="bodytext" style="padding: 12px;" align="justify"> 
<div class="subtitle_2nd" id="FullList">Full List of C++ Tutorials</div>
<ul>
   <li><a href="cpptut.html">C++ Home</a> </li>
   <li><a href="string.html">String</a> </li>
   <li><a href="constructor.html">Constructor</a> </li>
   <li><a href="operatoroverloading.html">Operator Overloading</a> </li>
   <li><a href="virtualfunctions.html">Virtual Functions</a></li>
   <li><a href="dynamic_cast.html">Dynamic Cast Operator</a></li>
   <li><a href="typecast.html">Type Cast Operators</a></li>
   <li><a href="autoptr.html">Class auto_ptr</a></li>   
   <li><a href="templates.html">Templates</a></li>
   <li><a href="references.html">References for Built-in Types</a></li>
   <li><a href="valuevsreference.html">Pass by Value vs. Pass by Reference</a></li>
   <li><a href="memoryallocation.html">Memory Allocation</a></li>
   <li><a href="friendclass.html">Friend Functions and Friend Classes</a></li>
   <li><a href="functors.html">Functors (Function Objects)</a></li>
   <li><a href="statics.html">Static Variables and Static Class Members</a></li>
   <li><a href="exceptions.html">Exceptions</a></li>
   <li><a href="pointers.html">Pointers</a></li>
   <li><a href="pointers2.html">Pointers II</a></li>
   <li><a href="pointers3.html">Pointers III</a></li>
   <li><a href="smallprograms.html">Small Programs</a></li>
   <li><a href="linkedlist.html">Linked List Examples</a></li>
</ul>
</div>



<div class="bodytext" style="padding: 12px;" align="justify">
<div class="subtitle" id="linkedlistexamples">Linked List Examples</div>
<br />
<div class="subtitle_2nd" id="linkedlistexample1">Example 1</div>
<pre>

// linked list example (I) - using struct
#include &lt;iostream&gt;
#include &lt;cstring&gt;

using namespace std;

struct node * initNode( char *, int );
void displayNode( struct node * );
void displayList( struct node * );
void addNode( struct node * );
struct node * searchName( struct node *, char * );
void deleteNode( struct node * );
void insertNode( struct node * );
void deleteList( struct node * );

struct node {
   char name[20];
   int  id;
   struct node *next;
};

struct node *head = (struct node *) NULL;
struct node *tail = (struct node *) NULL;

// allocates memory for the node
// assign values to the member of the structure
struct node * initNode( char *name, int id )
{
   struct node *ptr = new node;

   // error? then just return
   if( ptr == NULL )                        
       return static_cast<struct node *>(NULL);       
   	// assign it 
	// then return pointer to ne node
   else {                                   
       strcpy( ptr->name, name );           
       ptr->id = id;                        
       return ptr;                   
   }
}

// adding to the end of list
void addNode( struct node *newnode )   
{
	// if there is no node, put it to head
	if( head == NULL ) {           
       head = newnode;                          
       tail = newnode;
	}

	// link in the new_node to the tail of the list
	// then mark the next field as the end of the list
	// adjust tail to point to the last node

	tail->next = newnode;         
	newnode->next = NULL;        
	tail = newnode;              
}
                                                            
void insertNode( struct node *newnode )
{
   struct node *temp, *prev;                 

   if( head == NULL ) {                     // if an empty list,  
       head = newnode;                      // set 'head' to it  
       tail = newnode;
       head->next = NULL;                   // set end of list to NULL 
       return;                             
   }

   temp = head;                             // start at beginning of list
					    // while currentname < newname 
   while( strcmp( temp->name, newnode->name) < 0 ) {
					    // to be inserted then 
          temp = temp->next;                // goto the next node in list
          if( temp == NULL )                // dont go past end of list  
              break;
   }
					    // set previous node before we insert  
					    // first check to see if its inserting   
   if( temp == head ) {		    	    // before the first node 
      newnode->next = head;                 // link next field to original list  
      head = newnode;                       // head adjusted to new node
   }
   else {				    // its not the first node
      prev = head;			    // start of the list,
      while( prev->next != temp ) {	    // will cycle to node before temp
          prev = prev->next;
      }
      prev->next = newnode;		    // insert node between prev and next 
      newnode->next = temp;
      if( tail == prev )		    // if the new node is inserted at the 
         tail = newnode;		    // end of the list the adjust 'end' 
   }
}

struct node * searchName( struct node *ptr, char *name )
{
    while( strcmp( name, ptr->name ) != 0 ) {   
       ptr = ptr->next;                          
       if( ptr == NULL )                         
          break;                                  
    }
    return ptr;                                  
}

struct node* searchId(struct node* ptr, int id) {
    while( id != ptr->id ) {    
       ptr = ptr->next;                          
       if( ptr == NULL )                          
          break;                                  
    }
    return ptr; 	
}

void reverse() {
	// we need at least two nodes for the reverse to have any effect
	if(head == NULL || head->next == NULL) return;

	// Starting 2nd list as 'me' and 'head' is now 'me->next'
	// and 'head->next' is pointing ot NULL
	// So, the 3rd list is now 'child' of 'me'
	node *parent = head;
	node *me = head->next;
	node *child = me->next;

	// convert head to tail
	head->next = NULL;

	// reverse pointer direction
	me->next = head;
	
	while(child != NULL){
		me->next = parent;
		parent = me;
		me = child;
		child = child->next;
	}
	// when me reached the tail
	// me becomes head
	head = me;
	// the head is now pointing to the 2nd last node
	head->next = parent;
}

void deleteNode( struct node *ptr )
{
  struct node *temp, *prev;
   temp = ptr;    // node to be deleted 
   prev = head;   // start of the list, will cycle to node before temp    

   if( temp == prev ) {                    // deleting first node?  
       head = head->next;                  // moves head to next node     
       if( tail == temp )                  // is it end, only one node?   
          tail = tail->next;               // adjust end as well          
       delete temp ;                       // free up space 
   }
   else {                                  // if not the first node, then 
       while( prev->next != temp ) {       // move prev to the node before
           prev = prev->next;              // the one to be deleted       
       }
       prev->next = temp->next;            // link previous node to next  
       if( tail == temp )                  // if this was the end node,   
           tail = prev;                    // then reset the end pointer  
      delete temp;                         // free up space
   }
}

void deleteList( struct node *ptr )
{
   struct node *temp;

   if( head == NULL ) return;   	// dont try to delete an empty list      

   if( ptr == head ) {			// if we are deleting the entire list    
       head = NULL;			// then reset head and    
       tail = NULL;			// end to empty                                     
   }
   else {
       temp = head;			// if its not the entire list, readjust end   
       while( temp->next != ptr )       // locate previous node to ptr   
           temp = temp->next;
       tail = temp;                     // set end to node before ptr   
   }

   while( ptr != NULL ) {		// while there are still nodes to delete      
      temp = ptr->next;			// record address of next node                 
      delete ptr;			// free this node                             
      ptr = temp;			// point to next node to be deleted           
   }
}


void displayNode( struct node *ptr ) {
	cout << ptr->id << ": " << ptr->name << endl;
}


void displayList( struct node *ptr ) {
   while( ptr != NULL )           {
      displayNode( ptr );           
      ptr = ptr->next;            
   }
}



#include &lt;iostream&gt;
using namespace std;

int main()
{
   	char* name;
   	int id, ch = 1;
   	struct node *ptr;

	// add
	ptr = initNode( "s1", 1 );
	addNode(ptr);
	ptr = initNode( "s2", 2 );
	addNode(ptr);
	ptr = initNode( "s3", 3 );
	addNode(ptr);
	ptr = initNode( "s4", 4 );
	addNode(ptr);
	ptr = initNode( "s5", 5 );
	addNode(ptr); 
	displayList(head);

	// delete
	name = "s2";
	ptr = searchName(head, name );
	if( ptr == NULL ) {
		cout << "\nName: " << name << " not found" << endl;
	}
	else {
		cout << "\nDeleting a node ...  ";
	    displayNode(ptr);
		deleteNode( ptr );
	}
	displayList(head);

	// insert
	name = "s2";
	id = 2;
	ptr = initNode( name, id );
	insertNode( ptr );
	cout << "\nInserting a node ...  ";
	displayNode(ptr);
	displayList(head);

	// reverse
	cout << "\nReversing the list ...  \n";
	reverse();
	displayList(head);

	// delete
	cout << "\nIn the end, deleting the list ...  \n";
	deleteList(head);
	displayList(head);
	return 0;
}
</pre>
<br />
<br />
<div class="subtitle_2nd" id="linkedlistexample2">Example 2</div>
<pre>
// linked list example (II) - using struct inside a class
 
#include &lt;iostream&gt;
#include &lt;string&gt;
using namespace std;

class list
{
public:
	struct node {
		int id;
		string name;
		struct node *next;
	} *head, *tail, *ptr;	

	list():head(NULL),tail(NULL){}	// constructor	
	~list();			// destructor

	struct list::node* searchName(struct list::node*, string);	
	struct list::node* searchId(struct list::node*, int);
	struct list::node* initNode(string, int);

	void reverse();
	void addNode( struct list::node*);
	void insertNode( struct list::node*);
	void deleteNode( struct list::node*);
	void deleteList( struct list::node*);
	void displayList( struct list::node*)const ;
 	void displayNode( struct list::node*) const;	
};

list::~list() {
	node *current,*temp;
	current = head;
	temp = head;
	while(current != NULL) {
		current = current->next;
		delete temp;
		temp = current;
	}
}

struct list::node* list::initNode(string s, int i) {
	struct node *ptr = new node;
 
	// error? then just return
	if( ptr == NULL )                         
		return static_cast<struct node *>(NULL);  
	// assign it 
	// then return pointer to ne node
	else {  
		ptr->name = s ;  
		ptr->id = i;                        
		return ptr;                         
	}
}

// adding to the end of list  
void list::addNode( struct node *newNode )  {
	// if there is no node, put it to head
	if( head == NULL ) {
		head = newNode;  
		tail = newNode;
	}
   
	// link in the new_node to the tail of the list
	// then mark the next field as the end of the list
	// adjust tail to point to the last node

	tail->next = newNode;       
	newNode->next = NULL;       
	tail = newNode;               
}

void list::insertNode( struct node *newnode ) {
   struct node *temp, *prev;                

   if( head == NULL ) {                     // if an empty list,         
       head = newnode;                      // set 'head' to it         
       tail = newnode;
       head->next = NULL;                   // set end of list to NULL     
       return;                                             
   }

   temp = head;                             // start at beginning of list 
					    // while currentname < newname 
   while( temp->name < newnode->name) {	    // to be inserted then 
          temp = temp->next;                // goto the next node in list  
          if( temp == NULL )                // dont go past end of list    
              break;
   }							 
					    // set previous node before we insert  
					    // first check to see if its inserting         
   if( temp == head ) {		    	    // before the first node 
      newnode->next = head;                 // link next field to original list    
      head = newnode;                       // head adjusted to new node          
   }
   else {				    // its not the first node
      prev = head;		    	    // start of the list, 
      while( prev->next != temp ) {	
          prev = prev->next;	    	    // will cycle to node before temp 
      }
      prev->next = newnode;                 // insert node between prev and next   
      newnode->next = temp;
      if( tail == prev )		    // if the new node is inserted at the  
         tail = newnode;		    // end of the list the adjust 'end'    
   }
}

struct list::node* list::searchName(struct node* ptr, string name) {
    while( name != ptr->name ) {    
       ptr = ptr->next;                          
       if( ptr == NULL )                          
          break;                                  
    }
    return ptr; 	
}

struct list::node* list::searchId(struct node* ptr, int id) {
    while( id != ptr->id ) {    
       ptr = ptr->next;                          
       if( ptr == NULL )                          
          break;                                  
    }
    return ptr; 	
}

void list::reverse() {
	// we need at least two nodes for the reverse to have any effect
	if(head == NULL || head->next == NULL) return;

	// Starting 2nd list as 'me' and 'head' is now 'me->next'
	// and 'head->next' is pointing ot NULL
	// So, the 3rd list is now 'child' of 'me'
	node *parent = head;
	node *me = head->next;
	node *child = me->next;

	// convert head to tail
	head->next = NULL;

	// reverse pointer direction
	me->next = head;
	
	while(child != NULL){
		me->next = parent;
		parent = me;
		me = child;
		child = child->next;
	}
	// when me reached the tail
	// me becomes head
	head = me;
	// the head is now pointing to the 2nd last node
	head->next = parent;
}
 

void list::deleteNode( struct list::node *ptr )
{
  struct node *temp, *prev;
   temp = ptr;    // node to be deleted 
   prev = head;   // start of the list, will cycle to node before temp    

   if( temp == prev ) {                    // deleting first node?  
       head = head->next;                  // moves head to next node     
       if( tail == temp )                  // is it end, only one node?   
          tail = tail->next;               // adjust end as well          
       delete temp ;                       // free up space 
   }
   else {                                  // if not the first node, then 
       while( prev->next != temp ) {       // move prev to the node before
           prev = prev->next;              // the one to be deleted       
       }
       prev->next = temp->next;            // link previous node to next  
       if( tail == temp )                  // if this was the end node,   
           tail = prev;                    // then reset the end pointer  
      delete temp;                         // free up space
   }
}

void list::deleteList( struct node *ptr )
{
   struct node *temp;

   if( head == NULL ) return;   	// dont try to delete an empty list      

   if( ptr == head ) {			// if we are deleting the entire list    
       head = NULL;			// then reset head and    
       tail = NULL;			// end to empty                                     
   }
   else {
       temp = head;			// if its not the entire list, readjust end   
       while( temp->next != ptr )       // locate previous node to ptr   
           temp = temp->next;
       tail = temp;                     // set end to node before ptr   
   }

   while( ptr != NULL ) {		// whilst there are still nodes to delete      
      temp = ptr->next;			// record address of next node                 
      delete ptr;			// free this node                             
      ptr = temp;			// point to next node to be deleted           
   }
}

void list::displayNode( struct list::node *ptr ) const
{
	cout << ptr->id << ": " << ptr->name << endl;
}

void list::displayList( struct list::node *ptr ) const
{
	if(!ptr) cout << "Nothing to display" << endl;
	while(ptr) {
		displayNode(ptr);
		ptr = ptr->next;
	}
}

int main()
{
	int id;
	string name;
 	list myList;
	list::node* ptr;

	// add
	ptr = myList.initNode( "s1", 1 );
	myList.addNode(ptr);
	ptr = myList.initNode( "s2", 2 );
	myList.addNode(ptr);
	ptr = myList.initNode( "s3", 3 );
	myList.addNode(ptr);
	ptr = myList.initNode( "s4", 4 );
	myList.addNode(ptr);
	ptr = myList.initNode( "s5", 5 );
	myList.addNode(ptr); 
	myList.displayList(myList.head);

	// delete
	name = "s2";
	ptr = myList.searchName( myList.head, name );
	if( ptr == NULL ) {
		cout << "\nName: " << name << " not found" << endl;
	}
	else {
		cout << "\nDeleting a node ...  ";
	    myList.displayNode(ptr);
		myList.deleteNode( ptr );
	}
	myList.displayList(myList.head);

	// insert
	name = "s2";
	id = 2;
	ptr = myList.initNode( name, id );
	myList.insertNode( ptr );
	cout << "\nInserting a node ...  ";
	myList.displayNode(ptr);
	myList.displayList(myList.head);

	// reverse
	cout << "\nReversing the list ...  \n";
	myList.reverse();
	myList.displayList(myList.head);

	// delete
	cout << "\nIn the end, deleting the list ...  \n";
	myList.deleteList(myList.head);
	myList.displayList(myList.head);
	return 0;
}
</pre>


<div id="rightpanel">
<div align="center">
</div></div>

<br /><br />
<div class="subtitle_2nd" id="FullList">Full List of C++ Tutorials</div>
<ul>
   <li><a href="cpptut.html">C++ Home</a> </li>
   <li><a href="string.html">String</a> </li>
   <li><a href="constructor.html">Constructor</a> </li>
   <li><a href="operatoroverloading.html">Operator Overloading</a> </li>
   <li><a href="virtualfunctions.html">Virtual Functions</a></li>
   <li><a href="dynamic_cast.html">Dynamic Cast Operator</a></li>
   <li><a href="typecast.html">Type Cast Operators</a></li>
   <li><a href="autoptr.html">Class auto_ptr</a></li>
   <li><a href="templates.html">Templates</a></li>
   <li><a href="references.html">References for Built-in Types</a></li>
   <li><a href="valuevsreference.html">Pass by Value vs. Pass by Reference</a></li>
   <li><a href="memoryallocation.html">Memory Allocation</a></li>
   <li><a href="friendclass.html">Friend Functions and Friend Classes</a></li>
   <li><a href="functors.html">Functors</a></li>
   <li><a href="statics.html">Static Variables and Static Class Members</a></li>
   <li><a href="exceptions.html">Exceptions</a></li>
   <li><a href="pointers.html">Pointers</a></li>
   <li><a href="pointers2.html">Pointers II</a></li>
   <li><a href="pointers3.html">Pointers III</a></li>
   <li><a href="smallprograms.html">Small Programs</a></li>
   <li><a href="linkedlist.html">Linked List Examples</a></li>
</ul>
<br /><br />



<script type="text/javascript"><!--
google_ad_client = "pub-5767010733052716";
/* 300x250, created 7/22/10 */
google_ad_slot = "4543448457";
google_ad_width = 300;
google_ad_height = 250;
//-->
</script>
<script type="text/javascript"
src="http://pagead2.googlesyndication.com/pagead/show_ads.js">
</script>
<br />


<br />
<br />
<br />


</div>
</div>
<div class="smallgraytext" id="footer"><a href="../index.html">Home</a>
| <a href="../about_us.html">About Us</a>
| <a href="../products.html">products</a>
| <a href="../our_services.html">Our Services</a>
| <a href="#">Contact Us</a>
| Bogotobogo &copy; 2010 | <a target="_blank" href="http://www.bogotobogo.com">Bogotobogo </a>
</div>
</div>
</div>
</body>
</html>
